// 题目大意：在一个环上有 n 个数 a_1,a_2,......,a_n，进行 n-1 次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。
// 你需要最大化你的得分。

#include <stdio.h>
#include <stdlib.h>

int maxscore(int *arr,int n){
    int **dp = (int**)malloc((2*n-1) * sizeof(int*));
    for(int i=0;i<2*n-1;i++){
        dp[i] = (int*)malloc((2*n-1) * sizeof(int));
    }
    // 初始化dp
    for(int i=0;i<2*n-1;i++){
        dp[i][i] = 0;
    }

    // 状态转移
    for(int i=1;i<n;i++){
        for(int j=0;j<2*n-i-1;j++){
            int max_s = 0;
            for(int k=j;k<j+i;k++){
                if(dp[j][k]+dp[k+1][j+i] > max_s){
                    max_s = dp[j][k]+dp[k+1][j+i];
                }
            }
            for(int k=j;k<=j+i;k++){
                max_s += arr[k%n];
            }
            dp[j][j+i] = max_s;
        }
    }

    int max_score = 0;
    for(int i=0;i<n;i++){
        if(dp[i][i+n-1]>max_score){
            max_score = dp[i][i+n-1];
        }
    }

    return max_score;
}

int main(){
    int arr[] = {1,9,9,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    int result = maxscore(arr,n);
    printf("%d",result);

    return 0;
}